{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximal Rectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #dynamic-programming #matrix #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #动态规划 #矩阵 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximalRectangle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大矩形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个仅包含&nbsp;<code>0</code> 和 <code>1</code> 、大小为 <code>rows x cols</code> 的二维二进制矩阵，找出只包含 <code>1</code> 的最大矩形，并返回其面积。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/14/maximal.jpg\" style=\"width: 402px; height: 322px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>最大矩形如上图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[\"0\"]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[\"1\"]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>rows == matrix.length</code></li>\n",
    "\t<li><code>cols == matrix[0].length</code></li>\n",
    "\t<li><code>1 &lt;= row, cols &lt;= 200</code></li>\n",
    "\t<li><code>matrix[i][j]</code> 为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximal-rectangle](https://leetcode.cn/problems/maximal-rectangle/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximal-rectangle](https://leetcode.cn/problems/maximal-rectangle/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"1\",\"0\",\"1\",\"0\",\"0\"],[\"1\",\"0\",\"1\",\"1\",\"1\"],[\"1\",\"1\",\"1\",\"1\",\"1\"],[\"1\",\"0\",\"0\",\"1\",\"0\"]]', '[[\"0\"]]', '[[\"1\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        # prepare the first floor\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if i == 0 or matrix[i][j] == \"0\":\n",
    "                    matrix[i][j] = int(matrix[i][j])\n",
    "                else:\n",
    "                    if matrix[i][j] == \"1\":\n",
    "                        matrix[i][j] = matrix[i-1][j] + 1\n",
    "        \n",
    "        max_area = 0\n",
    "        for i in range(len(matrix)):\n",
    "            # so to pop off all the items in the stack\n",
    "            heights = matrix[i] + [float('-inf')]\n",
    "            stack = [-1]\n",
    "            for j, h in enumerate(heights):\n",
    "                while stack and h < heights[stack[-1]]:\n",
    "                    idx = stack.pop()\n",
    "                    cur_h = heights[idx]\n",
    "                    width = j - stack[-1] - 1\n",
    "                    area = cur_h * width\n",
    "                    max_area = max(area, max_area)\n",
    "                stack.append(j)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        l_b = [0 for i in range(n)] # left bound\n",
    "        r_b = [n for i in range(n)] # right bound \n",
    "        h = [0 for i in range(n)] # height\n",
    "        max_rec = 0\n",
    "        for i in range(m):\n",
    "            c_l = 0 # current left bound\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '0':\n",
    "                    h[j] = 0\n",
    "                    l_b[j] = 0\n",
    "                    c_l = j+1\n",
    "                else:\n",
    "                    h[j] += 1\n",
    "                    l_b[j] = max(c_l, l_b[j])\n",
    "            c_r = n # current right bound\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if matrix[i][j] == '0':\n",
    "                    r_b[j] = n\n",
    "                    c_r = j\n",
    "                else:\n",
    "                    r_b[j] = min(c_r, r_b[j])\n",
    "                    # print(i, j, h[j]*(r_b[j]-l_b[j]))\n",
    "                    max_rec = max(max_rec, h[j]*(r_b[j]-l_b[j]))\n",
    "        return max_rec\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: 'List[List[str]]') -> 'int':\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        h, w = len(matrix), len(matrix[0])\n",
    "        m = []\n",
    "        for i in range(h):\n",
    "            tmp = []\n",
    "            for j in range(w):\n",
    "                tmp.append(0)\n",
    "            m.append(tmp)\n",
    "        for j in range(h):\n",
    "            for i in range(w):\n",
    "                if matrix[j][i] == '1':\n",
    "                    m[j][i] = m[j-1][i] + 1\n",
    "        res = 0\n",
    "        for row in m:\n",
    "            res = max(res, self.findLargestRectangle(row))\n",
    "        return res\n",
    "    \n",
    "    def findLargestRectangle(self, row):\n",
    "        height = 0\n",
    "        row.append(0)\n",
    "        stack = [-1]\n",
    "        for i in range(len(row)):\n",
    "            while row[i] < row[stack[-1]]:\n",
    "                h = row[stack.pop()]\n",
    "                w = i - stack[-1] - 1\n",
    "                height = max(height, h * w)\n",
    "            stack.append(i)\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        M, N = len(matrix), len(matrix[0])\n",
    "        \n",
    "        height = [0] * N\n",
    "        res = 0\n",
    "        for row in matrix:\n",
    "            for i in range(N):\n",
    "                if row[i] == '0':\n",
    "                    height[i] = 0\n",
    "                else:\n",
    "                    height[i] += 1\n",
    "            res = max(res, self.maxRectangleArea(height))\n",
    "        return res\n",
    "    def maxRectangleArea(self, height):\n",
    "        if not height:\n",
    "            return 0\n",
    "        res = 0\n",
    "        stack = list()\n",
    "        height.append(0)\n",
    "        for i in range(len(height)):\n",
    "            cur = height[i]\n",
    "            while stack and cur < height[stack[-1]]:\n",
    "                w = height[stack.pop()]\n",
    "                h = i if not stack else i - stack[-1] - 1\n",
    "                res = max(res, w * h)\n",
    "            stack.append(i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: 'List[List[str]]') -> 'int':\n",
    "        if len(matrix) == 0:\n",
    "            return 0\n",
    "        H, W = len(matrix), len(matrix[0])\n",
    "        left = [[0]* W for _ in range(H)]\n",
    "        right = [[0]* W for _ in range(H)]\n",
    "        fh = [0]* W\n",
    "        stack = [0]* (W+1)\n",
    "        index = [0]* (W+1)\n",
    "        ans = 0\n",
    "        for i in range(H):\n",
    "            stack[0] = 0\n",
    "            index[0] = -1\n",
    "            top = 0\n",
    "            for j in range(W):\n",
    "                fh[j] = fh[j] + 1 if matrix[i][j]==\"1\" else 0\n",
    "            for j in range(W):    \n",
    "                while top >=0 and stack[top] >= fh[j]:\n",
    "                    top-= 1\n",
    "                top += 1\n",
    "                stack[top] = fh[j]\n",
    "                index[top] = j\n",
    "                if top > 0:\n",
    "                    left[i][j] = j - index[top-1]\n",
    "                else:\n",
    "                    left[i][j] = 0\n",
    "            stack[0] = 0\n",
    "            index[0] = W\n",
    "            top = 0\n",
    "            for j in range(W-1,-1,-1):    \n",
    "                while top >=0 and stack[top] >= fh[j]:\n",
    "                    top-= 1\n",
    "                top += 1\n",
    "                stack[top] = fh[j]\n",
    "                index[top] = j\n",
    "                if top > 0:\n",
    "                    right[i][j] = index[top-1] - j\n",
    "                else:\n",
    "                    right[i][j] = 0\n",
    "            for j in range(W):\n",
    "                ans = max(ans,(left[i][j]+right[i][j]-1)*fh[j])\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if matrix == []:\n",
    "            return 0\n",
    "        rows = len(matrix)\n",
    "        cloumns = len(matrix[0])\n",
    "        dp = [[0] * cloumns for i in range(rows)]\n",
    "        \n",
    "        dp[0][0] = int(matrix[0][0])\n",
    "        for i in range(1,cloumns):\n",
    "            if matrix[0][i] == '1':\n",
    "                # dp[0][i] = dp[0][i - 1] + 1\n",
    "                dp[0][i] = 1\n",
    "            else:\n",
    "                dp[0][i] = 0\n",
    "        for i in range(1,rows):\n",
    "            if matrix[i][0] == '1':\n",
    "                dp[i][0] = dp[i - 1][0] + 1\n",
    "            else:\n",
    "                dp[i][0] = 0\n",
    "        \n",
    "        for i in range(1, cloumns):\n",
    "            for j in range(1, rows):\n",
    "                if matrix[j][i] == '0':\n",
    "                    dp[j][i] = 0\n",
    "                else:\n",
    "                    dp[j][i] = dp[j-1][i] + 1\n",
    "        maxNum = 0\n",
    "        for i in range(rows):\n",
    "            if maxNum < self.chooseMax(dp[i]):\n",
    "                maxNum = self.chooseMax(dp[i])\n",
    "            print(maxNum)\n",
    "        print(dp)\n",
    "        \n",
    "        return maxNum\n",
    "    \n",
    "    def chooseMax(self, nums):\n",
    "        maxNum = 0\n",
    "        for i in set(nums):\n",
    "            count = 0\n",
    "            for j in nums:\n",
    "                if j >= i:\n",
    "                    count += 1\n",
    "                    if maxNum < count * i:\n",
    "                        maxNum = count * i\n",
    "                else:\n",
    "                    count = 0\n",
    "        return maxNum\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    # 把问题转化为子问题——最大子段和maxSequence()\n",
    "    def maximalRectangle(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        r = len(matrix)\n",
    "        if r == 0:\n",
    "            return 0\n",
    "        c = len(matrix[0])\n",
    "\n",
    "        # a数组将matrix中的0全部替换为-无穷\n",
    "        a = [[0]*c for i in range(r)]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if matrix[i][j] == \"0\":\n",
    "                    a[i][j] = -1e6\n",
    "                else:\n",
    "                    a[i][j] = 1\n",
    "                \n",
    "        \n",
    "        # b[i][j] 存第j列中前i行的子段和\n",
    "        b = [[0]*c for i in range(r+1)]\n",
    "        for j in range(c):\n",
    "            for i in range(r):\n",
    "                if i == 0:\n",
    "                    b[i][j] = a[i][j]\n",
    "                else:\n",
    "                    b[i][j] = b[i-1][j] + a[i][j]\n",
    "        \n",
    "        # 按照行进行合并 第i行到第j行合并为一行  \n",
    "        val = [0] * (c+1)\n",
    "        ans = 0      \n",
    "        for i in range(r):\n",
    "            for j in range(i,r):\n",
    "                minp = 0  ### fixed\n",
    "                maxp = -1e12\n",
    "                f = [0] * (c+1)   ### fixed\n",
    "                for k in range(c):\n",
    "                    if k == 0:\n",
    "                        f[k] = b[j][k] - b[i-1][k]\n",
    "                    else:\n",
    "                        f[k] += f[k-1] + (b[j][k] - b[i-1][k])  ### fixed\n",
    "                    maxp = max(maxp, f[k]-minp) ### fixed\n",
    "                    minp = min(minp, f[k])  ### fixed\n",
    "                # print(i,j,f)\n",
    "                ans = max(ans,maxp)\n",
    "        return int(ans)\n",
    "\n",
    "\n",
    "# if __name__ == \"__main__\":\n",
    "#     matrix = [\n",
    "#         [\"1\",\"0\",\"1\",\"0\",\"0\"],\n",
    "#         [\"1\",\"0\",\"1\",\"1\",\"1\"],\n",
    "#         [\"1\",\"1\",\"1\",\"1\",\"1\"],\n",
    "#         [\"1\",\"0\",\"0\",\"1\",\"0\"]\n",
    "#     ]\n",
    "#     print(Solution.maximalRectangle(None, matrix))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix):\n",
    "        \"\"\"\n",
    "        :type matrix: List[List[str]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        msum = [[int(j) for j in i] for i in matrix]\n",
    "        maxy = len(matrix)\n",
    "        maxx = 0 if len(matrix)==0 else len(matrix[0])\n",
    "        for i in range(maxy):\n",
    "            for j in range(maxx):\n",
    "                msum[i][j] = msum[i][j]+(0 if i==0 else msum[i-1][j])+(0 if j==0 else msum[i][j-1])-(0 if i==0 or j==0 else msum[i-1][j-1])\n",
    "        \n",
    "        def isrect(y0,x0,y1,x1):\n",
    "            return msum[y1][x1] - (0 if y0==0 else msum[y0-1][x1]) - (0 if x0==0 else msum[y1][x0-1]) + (0 if x0==0 or y0==0 else msum[y0-1][x0-1]) == (x1-x0+1)*(y1-y0+1)\n",
    "        \n",
    "        def bimin(f, al, ar):\n",
    "            while al<ar:\n",
    "                am = (al+ar)//2\n",
    "                if f(am): ar = am\n",
    "                else: al = am+1\n",
    "            return ar\n",
    "        def bimax(f, al, ar):\n",
    "            while al<ar:\n",
    "                am = (al+ar+1)//2\n",
    "                if f(am): al = am\n",
    "                else: ar = am-1\n",
    "            return al\n",
    "        \n",
    "        areamax = 0\n",
    "        for i in range(maxy):\n",
    "            for j in range(maxx):\n",
    "                if matrix[i][j]=='1':\n",
    "                    imax = bimax(lambda ni:isrect(i,j,ni,j),i,maxy-1)\n",
    "                    jmin = bimin(lambda nj:isrect(i,nj,imax,j),0,j)\n",
    "                    jmax = bimax(lambda nj:isrect(i,j,imax,nj),j,maxx-1)\n",
    "                    areamax = max(areamax,(imax-i+1)*(jmax-jmin+1))\n",
    "        \n",
    "        return areamax\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRectangleArea(self, heights: 'List[int]') -> 'int':\n",
    "        tot = len(heights)\n",
    "        area = 0\n",
    "        next_less, previous_less = [-1]*tot, [-1]*tot\n",
    "        s1, s2 = [], []\n",
    "        for i in range(tot):\n",
    "            while s1 and heights[s1[-1]] > heights[i]:\n",
    "                cur_idx = s1.pop()\n",
    "                next_less[cur_idx] = i\n",
    "            s1.append(i)\n",
    "\n",
    "            while s2 and heights[s2[-1]] > heights[i]:\n",
    "                s2.pop()\n",
    "            previous_less[i] = s2[-1] if s2 else -1\n",
    "            s2.append(i)\n",
    "\n",
    "        for i in range(tot):\n",
    "            if previous_less[i] == -1 and next_less[i] == -1:\n",
    "                width = tot\n",
    "            elif previous_less[i] == -1 and next_less[i] == -1:\n",
    "                width = next_less[i] - 0\n",
    "            elif previous_less[i] != -1 and next_less[i] == -1:\n",
    "                width = tot - previous_less[i] - 1\n",
    "            else:\n",
    "                width = next_less[i] - previous_less[i] - 1\n",
    "            area = max(area, width*heights[i])\n",
    "        return area\n",
    "    \n",
    "    def maximalRectangle(self, matrix: 'List[List[str]]') -> 'int':\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        row = len(matrix)\n",
    "        col = len(matrix[0])\n",
    "        heights = list(map(int, matrix[0]))\n",
    "        res = self.largestRectangleArea(heights)\n",
    "        \n",
    "        for i in range(1, row):\n",
    "            for j in range(0, col):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    heights[j] += 1\n",
    "                else:\n",
    "                    heights[j] = 0\n",
    "            res = max(res, self.largestRectangleArea(heights))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix: return 0\n",
    "        def max_square(nums):\n",
    "            stark = []\n",
    "            res = 0\n",
    "            nums = [0] + nums+ [0]\n",
    "            for i, num in enumerate(nums):\n",
    "                while stark and num <stark[-1][-1]:\n",
    "                    idx, height = stark.pop()\n",
    "                    res = max(res, height * (i-1-stark[-1][0]))\n",
    "                stark.append([i, num])\n",
    "            return res\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        dp = [0] * n \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[j] = dp[j] +1 if matrix[i][j] == '1' else 0\n",
    "            res = max(res, max_square(dp))\n",
    "        return res \n",
    "      \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        def merge(dp):\n",
    "            stack = []\n",
    "            dp = [0] + dp + [0]\n",
    "            res = 0\n",
    "            for i in range(len(dp)):\n",
    "                while stack and dp[stack[-1]] > dp[i]:\n",
    "                    tmp = stack.pop()\n",
    "                    res = max(res, (i - stack[-1] - 1) * dp[tmp])\n",
    "                stack.append(i)\n",
    "            return res\n",
    "        maxarea = 0\n",
    "        dp = [0] * len(matrix[0])\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "\n",
    "                # update the state of this row's histogram using the last row's histogram\n",
    "                # by keeping track of the number of consecutive ones\n",
    "\n",
    "                dp[j] = dp[j] + 1 if matrix[i][j] == '1' else 0\n",
    "\n",
    "            # update maxarea with the maximum area from this row's histogram\n",
    "            maxarea = max(maxarea, merge(dp))\n",
    "        return maxarea\n",
    "\n",
    "        return merge(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix: return 0\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        left = [0] * n # initialize left as the leftmost boundary possible\n",
    "        right = [n] * n # initialize right as the rightmost boundary possible\n",
    "        height = [0] * n\n",
    "\n",
    "        maxarea = 0\n",
    "\n",
    "        for i in range(m):\n",
    "\n",
    "            cur_left, cur_right = 0, n\n",
    "            # update height\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1': height[j] += 1\n",
    "                else: height[j] = 0\n",
    "            # update left\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1': left[j] = max(left[j], cur_left)\n",
    "                else:\n",
    "                    left[j] = 0\n",
    "                    cur_left = j + 1\n",
    "            # update right\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if matrix[i][j] == '1': right[j] = min(right[j], cur_right)\n",
    "                else:\n",
    "                    right[j] = n\n",
    "                    cur_right = j\n",
    "            # update the area\n",
    "            for j in range(n):\n",
    "                maxarea = max(maxarea, height[j] * (right[j] - left[j]))\n",
    "\n",
    "        return maxarea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix: return 0\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "\n",
    "        left = [0] * n # initialize left as the leftmost boundary possible\n",
    "        right = [n] * n # initialize right as the rightmost boundary possible\n",
    "        height = [0] * n\n",
    "\n",
    "        maxarea = 0\n",
    "\n",
    "        for i in range(m):\n",
    "\n",
    "            cur_left, cur_right = 0, n\n",
    "            # update height\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1': height[j] += 1\n",
    "                else: height[j] = 0\n",
    "            # update left\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1': left[j] = max(left[j], cur_left)\n",
    "                else:\n",
    "                    left[j] = 0\n",
    "                    cur_left = j + 1\n",
    "            # update right\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if matrix[i][j] == '1': right[j] = min(right[j], cur_right)\n",
    "                else:\n",
    "                    right[j] = n\n",
    "                    cur_right = j\n",
    "            # update the area\n",
    "            for j in range(n):\n",
    "                maxarea = max(maxarea, height[j] * (right[j] - left[j]))\n",
    "\n",
    "        return maxarea"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle_v2(self, matrix: List[List[str]]) -> int:\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0]) if len(matrix) != 0 else 0\n",
    "        res = 0\n",
    "        dp = [[0] * cols for _ in range(rows)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if matrix[i][j] == \"0\": continue\n",
    "                cur = dp[i][j] = dp[i][j - 1] + 1 if j else 1\n",
    "\n",
    "                for k in range(i, -1, -1):\n",
    "                    cur = min(cur, dp[k][j])\n",
    "                    res = max(res, cur * (i - k + 1))\n",
    "        return res\n",
    "\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0]) if len(matrix) != 0 else 0\n",
    "        res = 0\n",
    "        dp = [0] * cols\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                dp[j] = dp[j] + 1 if matrix[i][j] != \"0\" else 0\n",
    "\n",
    "            res = max(res, self.largestRectangleArea(dp))\n",
    "        return res\n",
    "\n",
    "    def largestRectangleArea(self, heights: List[int]) -> int:\n",
    "        res, cur = 0, 0\n",
    "        stack = []\n",
    "        heights = [0] + heights + [0]\n",
    "        for i in range(len(heights)):\n",
    "            while len(stack) != 0 and heights[i] < heights[stack[-1]]:\n",
    "                cur = heights[stack.pop()]\n",
    "                res = max(res, cur * (i - stack[-1] - 1))\n",
    "            stack.append(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        dp = [[] for _ in range(len(matrix))]\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if j == 0:\n",
    "                    elem = int(matrix[i][j])\n",
    "                elif matrix[i][j] == \"0\":\n",
    "                    elem = 0\n",
    "                else:\n",
    "                    elem = dp[i][j - 1] + 1\n",
    "                dp[i].append(elem)\n",
    "        max_area = 0\n",
    "        for i in range(len(dp)):\n",
    "            for j in range(len(dp[0])):\n",
    "                height = 1\n",
    "                width = dp[i][j]\n",
    "                while height <= i + 1:\n",
    "                    width = min(width, dp[i - height + 1][j])\n",
    "                    max_area = max(max_area, width * height)\n",
    "                    height += 1\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.row_num = 0\n",
    "        self.col_num = 0\n",
    "        self.width = None\n",
    "        self.area = None\n",
    "\n",
    "    def maximalRectangle(self, matrix):\n",
    "        self.row_num = len(matrix)\n",
    "        if self.row_num == 0:\n",
    "            return 0\n",
    "        self.col_num = len(matrix[0])\n",
    "        self.width = [[0 for _ in range(self.col_num)] for _ in range(self.row_num)]\n",
    "        self.area = [[0 for _ in range(self.col_num)] for _ in range(self.row_num)]\n",
    "        for i in range(self.row_num):\n",
    "            for j in range(self.col_num):\n",
    "                if matrix[i][j] == \"1\" and self.width[i][j] == 0:\n",
    "                        self.width[i][j] = self._max_right_range(matrix, i, j)\n",
    "\n",
    "        self.area[0] = self.width[0][::]\n",
    "        for i in range(1, self.row_num):\n",
    "            for j in range(self.col_num):\n",
    "                self.area[i][j] = self._max_area(i, j)\n",
    "\n",
    "        return max((max(e) for e in self.area))\n",
    "\n",
    "    def _max_right_range(self, matrix, start_i, start_j):\n",
    "        if self.width[start_i][start_j] != 0:\n",
    "            return self.width[start_i][start_j]\n",
    "\n",
    "        if start_j == self.col_num - 1:\n",
    "            self.width[start_i][start_j] = 1\n",
    "            return 1\n",
    "\n",
    "        if matrix[start_i][start_j + 1] == \"1\":\n",
    "            width = 1 + self._max_right_range(matrix, start_i, start_j + 1)\n",
    "            self.width[start_i][start_j] = width\n",
    "            return width\n",
    "        else:\n",
    "            self.width[start_i][start_j] = 1\n",
    "            return 1\n",
    "\n",
    "    def _max_area(self, end_i, end_j):\n",
    "        min_width = self.width[end_i][end_j]\n",
    "        max_area = min_width\n",
    "        for i in range(1, end_i+1):\n",
    "            min_width = min(min_width, self.width[end_i-i][end_j])\n",
    "            if min_width == 0:\n",
    "                break\n",
    "            max_area = max(max_area, min_width * (i + 1))\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        widths = [[] for i in range(len(matrix))]\n",
    "        for row in range(len(matrix)):\n",
    "            start, end = 0, -1\n",
    "            for j in range(len(matrix[row])):\n",
    "                if matrix[row][j] == '1':\n",
    "                    if end == -1:\n",
    "                        start, end = j, j\n",
    "                    else:\n",
    "                        end += 1\n",
    "                else:\n",
    "                    if end != -1:\n",
    "                        widths[row].append((start, end))\n",
    "                    end = -1\n",
    "            if end != -1:\n",
    "                widths[row].append((start, end))\n",
    "\n",
    "\n",
    "        heights = [[] for i in range(len(matrix[0]))]\n",
    "        for col in range(len(matrix[0])):\n",
    "            start, end = 0, -1\n",
    "            for j in range(len(matrix)):\n",
    "                if matrix[j][col] == '1':\n",
    "                    if end == -1:\n",
    "                        start, end = j, j\n",
    "                    else:\n",
    "                        end += 1\n",
    "                else:\n",
    "                    if end != -1:\n",
    "                        heights[col].append((start, end))\n",
    "                    end = -1\n",
    "            if end != -1:\n",
    "                heights[col].append((start, end))\n",
    "\n",
    "        res = 0\n",
    "        for 列号, 一列的所有竖段s in enumerate(heights):\n",
    "            for 竖段 in 一列的所有竖段s:\n",
    "                竖段开始行 = 竖段[0]\n",
    "                竖段结束行 = 竖段[1]\n",
    "                宽 = [0, len(matrix[0])]\n",
    "                for i in range(竖段开始行, 竖段结束行+1):\n",
    "                    for 横段 in widths[i]:\n",
    "                        横段开始列 = 横段[0]\n",
    "                        横段结束列 = 横段[1]\n",
    "\n",
    "                        if 横段开始列 <= 列号 and 横段结束列 >= 列号:\n",
    "                            宽[0] = max(横段开始列, 宽[0])\n",
    "                            宽[1] = min(横段结束列, 宽[1])\n",
    "\n",
    "                            res = max(res, (宽[1] - 宽[0] + 1) * (i - 竖段开始行 + 1))\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        s = 0\n",
    "        tmap = {}\n",
    "        for i, rows in enumerate(matrix):\n",
    "            for j, col in enumerate(rows):\n",
    "                if col == \"0\":\n",
    "                    if i not in tmap.keys():\n",
    "                        tmap[i] = {}\n",
    "                    tmap[i][j] = 0\n",
    "                else:\n",
    "                    a = 1\n",
    "                    if j > 0:\n",
    "                        a = tmap[i][j-1] + a\n",
    "                    if i not in tmap.keys():\n",
    "                        tmap[i] = {}\n",
    "                    tmap[i][j] = a\n",
    "                    s = max(a, s)\n",
    "                    if i > 0:\n",
    "                        tb = a\n",
    "                        for ai in range(1, i+1):\n",
    "                            if matrix[i-ai][j] == \"0\":\n",
    "                                break\n",
    "                            tb = min(tb, tmap[i - ai][j])\n",
    "                            s = max(s, tb * (ai + 1))\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        n = len(matrix) # rows\n",
    "        m = len(matrix[0]) # cols\n",
    "        dleft = {}\n",
    "        for i in range(n):\n",
    "            cumul = 0\n",
    "            dleft[i] = {}\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    cumul += 1\n",
    "                else:\n",
    "                    cumul = 0\n",
    "                # print(i, j, matrix[i][j], cumul)\n",
    "                dleft[i][j] = cumul\n",
    "        # print(dleft)\n",
    "        max_area = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                k = i\n",
    "                wid = dleft[i][j]\n",
    "                while (k >= 0 and matrix[k][j] == \"1\"):\n",
    "                    wid = min(wid, dleft[k][j])\n",
    "                    area = wid * (i-k+1)\n",
    "                    # print(i, j, k, dleft[k][j], area)\n",
    "                    if max_area < area:\n",
    "                        max_area = area\n",
    "                    k -= 1\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        rows=len(matrix)\n",
    "        cols=len(matrix[0])\n",
    "        dp=[[(0,0)]*(cols+1) for _ in range(rows+1)]\n",
    "        res=0\n",
    "        for i in range(1,rows+1):\n",
    "            for j in range(1,cols+1):\n",
    "                if matrix[i-1][j-1]=='1':\n",
    "                    dp[i][j]=(dp[i][j-1][0]+1,dp[i-1][j][1]+1)\n",
    "                    w=dp[i][j][0]\n",
    "                    h=dp[i][j][1]\n",
    "                    for k in range(h):\n",
    "                        w=min(w,dp[i-k][j][0])\n",
    "                        res=max((k+1)*w,res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        max_area = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] != \"1\":\n",
    "                    matrix[i][j] = (0, 0)\n",
    "                    continue\n",
    "\n",
    "                if i == 0:\n",
    "                    up = 1\n",
    "                else:\n",
    "                    up = matrix[i-1][j][0] + 1\n",
    "\n",
    "                if j == 0:\n",
    "                    left = 1\n",
    "                else:\n",
    "                    left = matrix[i][j-1][1] +1\n",
    "                matrix[i][j] = (up, left)\n",
    "                \n",
    "                min_height = up\n",
    "                max_area = max(max_area, up)\n",
    "                for k in range(1, left):\n",
    "                    min_height = min(min_height, matrix[i][j-k][0])\n",
    "                    max_area = max(max_area, (k+1) * min_height)\n",
    "                # print(i , j, max_area)\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:#特判\n",
    "            return 0\n",
    "        m=len(matrix)\n",
    "        \n",
    "        n=len(matrix[0])\n",
    "        Rectangle=0\n",
    "        #前缀和一层一层的堆高度\n",
    "        for i in range(1,m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]=='1':\n",
    "                    matrix[i][j]=str(int(matrix[i-1][j])+1)\n",
    "        #看每一层能得到的最大矩形\n",
    "        for i in range(m):\n",
    "            Rectangle=max(Rectangle,self.MonoStack(list(map(int,matrix[i]))))\n",
    "        return Rectangle\n",
    "        \n",
    "    #单调栈求每一层的最大矩形，模仿84题\n",
    "    def MonoStack(self,arraylist):\n",
    "        arraylist=[0]+arraylist+[0]\n",
    "        size=len(arraylist)\n",
    "        stack=[]\n",
    "        max_rectangle=0\n",
    "        for i in range(size):\n",
    "            while stack and arraylist[stack[-1]]>arraylist[i]:\n",
    "                cur=stack.pop()\n",
    "                max_rectangle=max(max_rectangle,(i-stack[-1]-1)*arraylist[cur])\n",
    "            stack.append(i)\n",
    "        return max_rectangle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        n = len(matrix[0])\n",
    "        if n == 0:\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        dp = [[[0, 0]] * n for _ in range(m)]\n",
    "        if matrix[0][0] == '1':\n",
    "            dp[0][0] = [1, 1]   # width/height\n",
    "            ans = 1  # 不要漏了对ans赋值\n",
    "        for j in range(1, n):\n",
    "            if matrix[0][j] == '1':\n",
    "                dp[0][j] = [dp[0][j - 1][0] + 1, 1]\n",
    "                ans = max(ans, dp[0][j][0])  # 不要漏了对ans赋值\n",
    "        for i in range(1, m):\n",
    "            if matrix[i][0] == '1':\n",
    "                dp[i][0] = [1, dp[i - 1][0][1] + 1]\n",
    "                ans = max(ans, dp[i][0][1])  # 不要漏了对ans赋值\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    w, h = dp[i][j - 1][0] + 1, dp[i - 1][j][1] + 1\n",
    "                    dp[i][j] = [w, h]\n",
    "                    if w * h > ans:\n",
    "                        # 从当前行逐行向上计算矩形面积，宽度取每行最小值\n",
    "                        # 当前行也要算，高度为1\n",
    "                        for k in range(0, h):\n",
    "                            w = min(w, dp[i - k][j][0])\n",
    "                            ans = max(ans, w * (k + 1))\n",
    "        # print(dp)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #dp[i][j]=[w,h]，表示以(i,j)为终点的水平和垂直线段的长度\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if len(matrix) == 0 or len(matrix[0]) == 0:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        ans = 0\n",
    "        if matrix[0][0] == '1':\n",
    "            dp[0][0] = [1, 1]\n",
    "            ans = 1\n",
    "        for j in range(1, n):\n",
    "            if matrix[0][j] == '1':\n",
    "                dp[0][j] = [dp[0][j - 1][0] + 1, 1]\n",
    "                ans = max(ans, dp[0][j][0])\n",
    "        for i in range(1, m):\n",
    "            if matrix[i][0] == '1':\n",
    "                dp[i][0] = [1, dp[i - 1][0][1] + 1]\n",
    "                ans = max(ans, dp[i][0][1])\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    w, h = dp[i][j - 1][0] + 1, dp[i - 1][j][1] + 1\n",
    "                    dp[i][j] = [w, h]\n",
    "                    if w * h > ans:\n",
    "                        #从当前行逐行向上计算矩形面积，取宽度最小值\n",
    "                        #不需要考虑dp[i-1][j-1]，而是向上遍历每行j列宽度\n",
    "                        for k in range(h):\n",
    "                            w = min(w, dp[i - k][j][0])\n",
    "                            ans = max(ans, w * (k + 1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix or not matrix[0]:\n",
    "            return 0\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        # dp[i][j] 表示(i, j)点 [向左最大距离， 向上最大距离]\n",
    "        dp = [[[0, 0] for _ in range(n)] for _ in range(m)]\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == \"1\":\n",
    "                    if i == 0 and j == 0:\n",
    "                        dp[i][j][0] = 1\n",
    "                        dp[i][j][1] = 1\n",
    "                    elif i == 0:\n",
    "                        dp[i][j][0] = dp[i][j - 1][0] + 1\n",
    "                        dp[i][j][1] = 1\n",
    "                    elif j == 0:\n",
    "                        dp[i][j][0] = 1\n",
    "                        dp[i][j][1] = dp[i - 1][j][1] + 1\n",
    "                    else:\n",
    "                        dp[i][j][0] = dp[i][j - 1][0] + 1\n",
    "                        dp[i][j][1] = dp[i - 1][j][1] + 1\n",
    "                    # 计算以(i, j)为右下角的矩形的最大面积\n",
    "                    min_col, row = dp[i][j][0], dp[i][j][1]\n",
    "                    for k in range(row):\n",
    "                        min_col = min(min_col, dp[i - k][j][0])\n",
    "                        res = max(res, min_col * (k + 1))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        def maxHeight(heights):\n",
    "            heights = [0]+heights+[0]\n",
    "            stack = [0]\n",
    "            res = 0\n",
    "            for i in range(1, len(heights)):\n",
    "                while stack and heights[stack[-1]]>heights[i]:\n",
    "                    cur = stack.pop()\n",
    "                    res = max(res, heights[cur]*(i-stack[-1]-1))\n",
    "                stack.append(i)\n",
    "            return res\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        cur = matrix.pop(0)\n",
    "        cur = list(map(int, cur))\n",
    "        res = maxHeight(cur)\n",
    "        while matrix:\n",
    "            this = matrix.pop(0)\n",
    "            for i in range(len(this)):\n",
    "                if this[i]=='1':\n",
    "                    cur[i]+=1\n",
    "                else:\n",
    "                    cur[i] = 0\n",
    "            res = max(res, maxHeight(cur))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return \n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "                if matrix[i][j] == 0:continue \n",
    "                else:\n",
    "                    if i > 0 and matrix[i- 1][j] > 0:\n",
    "                        matrix[i][j] = matrix[i- 1][j] + 1\n",
    "        def maxHistogram(mat):\n",
    "            mat = [0] + mat + [0]\n",
    "            n = len(mat)\n",
    "            stack = []\n",
    "            max_area = 0\n",
    "            for i in range(len(mat)):\n",
    "                while stack and  mat[i] < mat[stack[-1]]:\n",
    "                    curr_height = mat[stack.pop()]\n",
    "                    curr_width = i -stack[-1] - 1\n",
    "                    max_area = max(max_area, curr_height * curr_width)\n",
    "                stack.append(i)\n",
    "            return max_area\n",
    "        \n",
    "        max_area = 0\n",
    "        for mat in matrix:\n",
    "            max_area = max(max_area, maxHistogram(mat))\n",
    "        return max_area\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestRes(self, heights: List[int]) -> int:\n",
    "        heights = [0] + heights + [0]\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for i in range(len(heights)):\n",
    "            while stack and heights[stack[-1]] > heights[i]:\n",
    "                a = stack.pop()\n",
    "                res=max(res, (i-stack[-1]-1)*heights[a])\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        resmax = 0\n",
    "        while matrix:\n",
    "            heights = [0] * len(matrix[0])\n",
    "            for j in range(len(matrix[0])):\n",
    "                height = 0\n",
    "                for i in range(len(matrix)):\n",
    "                    if int(matrix[i][j]) == 1:\n",
    "                        heights[j] += 1\n",
    "                        #print(height) \n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                #print(heights, height)                 \n",
    "                resmax = max(resmax, self.largestRes(heights))\n",
    "                #print(\"res\", resmax)\n",
    "            matrix.pop(0)\n",
    "        return resmax\n",
    "                             \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def test(self,arr:list[int])->int:\n",
    "        stack,dic,S=[],{},[0]\n",
    "        for i in range(len(arr)):\n",
    "            while len(stack)>0 and arr[stack[-1][0]]>arr[i]:\n",
    "                p=stack.pop()\n",
    "                left=-1 if len(stack)==0 else stack[-1][-1]\n",
    "                for j in p: dic[j]=[left,i]\n",
    "            if len(stack)>0 and arr[stack[-1][0]]==arr[i]:\n",
    "                stack[-1].append(i)\n",
    "            else:\n",
    "                stack.append([i])\n",
    "        while len(stack)>0:\n",
    "            p=stack.pop()\n",
    "            left=-1 if len(stack)==0 else stack[-1][-1]\n",
    "            for j in p:\n",
    "                dic[j]=[left,len(arr)]\n",
    "        for i in range(len(arr)):\n",
    "            S.append(arr[i]*(dic[i][1]-dic[i][0]-1))\n",
    "        return max(S)\n",
    "\n",
    "\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        S=[0]\n",
    "        for i in range(0,len(matrix)):\n",
    "            if i==0:\n",
    "                matrix[i]=[int(i) for i in matrix[i]]\n",
    "            else:\n",
    "                # 转化为面积矩阵\n",
    "                matrix[i]=[(i+int(j))*int(j) for i,j in zip(matrix[i-1],matrix[i])]\n",
    "            S.append(self.test(matrix[i]))\n",
    "        return max(S)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def test(self,arr:list[int])->int:\n",
    "        stack=[]\n",
    "        dic={}\n",
    "        S=[]\n",
    "        for i in range(len(arr)):\n",
    "            while len(stack)>0 and arr[stack[-1][0]]>arr[i]:\n",
    "                p=stack.pop()\n",
    "                left=-1 if len(stack)==0 else stack[-1][-1]\n",
    "                for j in p: dic[j]=[left,i]\n",
    "            if len(stack)>0 and arr[stack[-1][0]]==arr[i]:\n",
    "                stack[-1].append(i)\n",
    "            else:\n",
    "                stack.append([i])\n",
    "        while len(stack)>0:\n",
    "            p=stack.pop()\n",
    "            left=-1 if len(stack)==0 else stack[-1][-1]\n",
    "            for j in p:\n",
    "                dic[j]=[left,len(arr)]\n",
    "        for i in range(len(arr)):\n",
    "            S.append(arr[i]*(dic[i][1]-dic[i][0]-1))\n",
    "        return max(S)\n",
    "\n",
    "\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if matrix==[]: return 0\n",
    "        S=[]\n",
    "        matrix[0]=[int(i) for i in matrix[0]]\n",
    "        for i in range(1,len(matrix)):\n",
    "            matrix[i]=[(int(i)+int(j))*int(j) for i,j in zip(matrix[i-1],matrix[i])]\n",
    "        for i in matrix:\n",
    "            S.append(self.test(i))\n",
    "        return max(S)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "    \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if j == 0:\n",
    "                    matrix[i][j]=int(matrix[i][j])\n",
    "                else:\n",
    "                    matrix[i][j] = 0 if matrix[i][j]=='0' else matrix[i][j-1]+1\n",
    "        left = matrix\n",
    "        for j in range(m):\n",
    "            stack = []\n",
    "            up,down = [0]*n,[0]*n\n",
    "            for i in range(n):\n",
    "                while stack and left[stack[-1]][j]>=left[i][j]:\n",
    "                    stack.pop()\n",
    "                up[i] = -1 if not stack else stack[-1]\n",
    "                stack.append(i)\n",
    "            stack = []\n",
    "\n",
    "            for i in range(n-1,-1,-1):\n",
    "                while stack and left[stack[-1]][j]>=left[i][j]:\n",
    "                    stack.pop()\n",
    "                down[i] = n if not stack else stack[-1]\n",
    "                stack.append(i)\n",
    "\n",
    "            for i in range(n):\n",
    "                height = down[i]-up[i]-1\n",
    "                width = left[i][j]\n",
    "                ans = max(ans,height*width)\n",
    "        return ans\n",
    "\n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        row, col = len(matrix), len(matrix[0])\n",
    "        for c in range(col):\n",
    "            matrix[0][c] = int(matrix[0][c]) \n",
    "        for r in range(1, row):\n",
    "            for c in range(col):\n",
    "                matrix[r][c] = int(matrix[r][c]) \n",
    "                matrix[r][c] += matrix[r-1][c] if matrix[r][c] > 0 else 0\n",
    "        \n",
    "        def maxAreaInOneRow(height: List):\n",
    "            left, right = [0]*col, [col]*col\n",
    "            stack = []\n",
    "            for i, h in enumerate(height):\n",
    "                while stack and height[stack[-1]] >= h:\n",
    "                    right[stack[-1]] = i\n",
    "                    stack.pop()\n",
    "                left[i] = stack[-1] if stack else -1\n",
    "                stack.append(i)\n",
    "            return max((right[i] - left[i] - 1) * int(height[i]) for i in range(col))\n",
    "\n",
    "        Max = 0\n",
    "        for rowlist in matrix:\n",
    "            Max = max(Max, maxAreaInOneRow(rowlist))\n",
    "        return Max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        heights = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            matrix[i] = list(map(int, matrix[i]))\n",
    "        for j in range(n):\n",
    "            heights[0][j] = matrix[0][j]\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == 0: continue\n",
    "                heights[i][j] = heights[i - 1][j] + 1\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            cur_heights = [0] + heights[i] + [0]\n",
    "            stack = []\n",
    "            for j in range(n + 2):\n",
    "                while stack and stack[-1][0] > cur_heights[j]:\n",
    "                    cur_height, _ = stack.pop()\n",
    "                    right = j - 1\n",
    "                    left = stack[-1][1] + 1\n",
    "                    res = max(res, (right - left + 1) * cur_height)\n",
    "                stack.append((cur_heights[j], j))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        ans, m, n = 0, len(matrix), len(matrix[0]) if len(matrix) else 0\n",
    "        if -1 <m <2 and -1< n <2 : return max(list(map(int, sum(matrix, []))))\n",
    "        for i in range(m):\n",
    "            self.stack = list()\n",
    "            matrix[i] = list(map(int, matrix[i])) + [-1]\n",
    "            for j in range(n+ 1):\n",
    "                if matrix[i][j] and i > 0 and j < n:\n",
    "                    matrix[i][j] += matrix[i -1][j]\n",
    "                while self.stack and matrix[i][j] < matrix[i][self.stack[-1]]:\n",
    "                    height = matrix[i][self.stack.pop()]\n",
    "                    right, left = j, self.stack[-1] if self.stack else -1\n",
    "                    ans = max(ans, height * (right -left -1))\n",
    "                self.stack.append(j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = 0\n",
    "        for j in range(n):\n",
    "            if matrix[0][j] == '1':\n",
    "                matrix[0][j] = 1\n",
    "            else:\n",
    "                matrix[0][j] = 0\n",
    "        for i in range(1, m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j] == '1':\n",
    "                    matrix[i][j] = 1 + matrix[i - 1][j]\n",
    "                else:\n",
    "                    matrix[i][j] = 0\n",
    "        for nums in matrix:\n",
    "            nums = [0] + nums + [0]\n",
    "            stack = [0]\n",
    "            for i in range(1, len(nums)):\n",
    "                while stack and nums[i] < nums[stack[-1]]:\n",
    "                    cur = stack.pop()\n",
    "                    area = (i - stack[-1] - 1) * nums[cur]\n",
    "                    res = max(res, area)\n",
    "                stack.append(i)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        ans = 0\n",
    "        pre = [0] * m\n",
    "        suf = [m - 1] * m\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "                if i and matrix[i][j]:\n",
    "                    matrix[i][j] += matrix[i - 1][j]\n",
    "            stk = [(-1, -1)]\n",
    "            for j in range(m):\n",
    "                while stk and stk[-1][-1] >= matrix[i][j]:\n",
    "                    stk.pop()\n",
    "                pre[j] = stk[-1][0]\n",
    "                stk.append((j, matrix[i][j]))\n",
    "            stk = [(m, -1)]\n",
    "            for j in range(m - 1, -1, -1):\n",
    "                while stk and stk[-1][-1] >= matrix[i][j]:\n",
    "                    stk.pop()\n",
    "                suf[j] = stk[-1][0]\n",
    "                stk.append((j, matrix[i][j]))\n",
    "            for j in range(m):\n",
    "                ans = max(ans, (suf[j] - pre[j] - 1) * matrix[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            matrix[i][-1] = int(matrix[i][-1] )\n",
    "            for j in range(n-2,-1,-1):\n",
    "                matrix[i][j] = int(matrix[i][j])\n",
    "                if matrix[i][j]:\n",
    "                    matrix[i][j] = matrix[i][j + 1] + 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            stk = [[matrix[0][i],0]]\n",
    "            if (matrix[0][i]) > ans:\n",
    "                ans = matrix[0][i]\n",
    "            for j in range(1,m):\n",
    "                for h,loc in stk:\n",
    "                    tmp = min(matrix[j][i],h)*(j - loc + 1)\n",
    "                    if tmp > ans:\n",
    "                        ans = tmp\n",
    "                if (matrix[j][i]) > ans:\n",
    "                    ans = matrix[j][i]\n",
    "                tloc = j\n",
    "                while stk and matrix[j][i] <= stk[-1][0]:\n",
    "                    tloc = stk.pop()[1]\n",
    "                stk.append([matrix[j][i],tloc])\n",
    "        print(matrix)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        dp = matrix.copy()\n",
    "\n",
    "\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "             for j in range(n):\n",
    "                 dp[i][j] = int(dp[i][j])\n",
    "                 if dp[i][j] == 1:\n",
    "                    ans = 1\n",
    "                    # print(ans)\n",
    "                 if j !=0 and dp[i][j] == 1:\n",
    "                     dp[i][j] = dp[i][j-1] +1\n",
    "                \n",
    "        # print(ans)\n",
    "        # ans = 0\n",
    "        print(dp)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp[i][j] > 0:\n",
    "                    w = dp[i][j]\n",
    "                    for k in range(i,-1,-1):\n",
    "                        if dp[k][j]>0:\n",
    "                            w = min(dp[k][j],w)\n",
    "                            h = i-k+1\n",
    "                            ans = max(ans,w*h)\n",
    "                            # print(i,j,w,h)\n",
    "                        else:\n",
    "                            break\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        rows=len(matrix)\n",
    "        cols=len(matrix[0])\n",
    "        ms=0\n",
    "        matrix[0][0]=int(matrix[0][0])\n",
    "        for x in range(1,rows):\n",
    "            matrix[x][0]=int(matrix[x][0])+int(matrix[x-1][0])\n",
    "        for y in range(1,cols):\n",
    "            matrix[0][y]=int(matrix[0][y])+int(matrix[0][y-1])\n",
    "        for x in range(1,rows):\n",
    "            for y in range(1,cols):\n",
    "                matrix[x][y]=int(matrix[x][y])+int(matrix[x-1][y])+int(matrix[x][y-1])-int(matrix[x-1][y-1])\n",
    "        def checksquare(x1,y1,x2,y2):\n",
    "            sq=(x2-x1+1)*(y2-y1+1)\n",
    "            v=matrix[x2][y2]\n",
    "            if(x1>0):\n",
    "                v-=matrix[x1-1][y2]\n",
    "            if(y1>0):\n",
    "                v-=matrix[x2][y1-1]\n",
    "            if(x1>0 and y1>0):\n",
    "                v+=matrix[x1-1][y1-1]\n",
    "            if v==sq:\n",
    "                return v\n",
    "            return 0\n",
    "        for x1 in range(rows):\n",
    "            for x2 in range(x1,rows):\n",
    "                y0=-1\n",
    "                for y in range(cols):\n",
    "                    if(y0<0):\n",
    "                        s=checksquare(x1,y,x2,y)\n",
    "                        ms=max(ms,s)\n",
    "                        if(s>0):\n",
    "                            y0=y\n",
    "                    else:\n",
    "                        s=checksquare(x1,y0,x2,y)\n",
    "                        ms=max(ms,s)\n",
    "                        if(s<=0):\n",
    "                            y0=-1\n",
    "        return ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:\n",
    "            return 0\n",
    "        temp = [matrix[0]]\n",
    "        n = len(matrix)\n",
    "        m = len(matrix[0])\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            temp1 = []\n",
    "            for j in range(m):\n",
    "                if matrix[i][j] != \"0\":\n",
    "                    matrix[i][j] = int(matrix[i - 1][j]) + 1\n",
    "                temp1.append(str(matrix[i][j]))\n",
    "            temp.append(temp1)\n",
    "        for i in range(n):\n",
    "            temp[i] = ['0'] + temp[i] + ['0']\n",
    "            stack = []\n",
    "            for j in range(m+2):\n",
    "                while stack and int(temp[i][stack[-1]]) > int(temp[i][j]):\n",
    "                    temp2 = stack.pop()\n",
    "                    res = max(res, (j - stack[-1] - 1) * int(temp[i][temp2]))\n",
    "                stack.append(j)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        r = len(matrix)\n",
    "        c = len(matrix[0])\n",
    "        maps=[[0] * c for _ in range(r + 1)]\n",
    "        for i in range(r):\n",
    "            maps[i][0]=int(matrix[i][0])\n",
    "            for j in range(1, c):\n",
    "                matrix[i][j] = str((int(matrix[i][j-1] )+ 1)) if matrix[i][j]==\"1\" else \"0\"\n",
    "                maps[i][j]=int(matrix[i][j])\n",
    "        ans=0\n",
    "        for j in range(c):\n",
    "            st=[-1]\n",
    "            for i in range(r+1):\n",
    "                while st[-1]!=-1 and maps[i][j] < maps[st[-1]][j]:\n",
    "                    temp=st.pop()\n",
    "                    ans = max(ans, (i - st[-1] -1) * maps[temp][j] )\n",
    "                st.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        #按行迭代就是最大矩形问题，1的数量就是高多\n",
    "        def maxRectangle(heights):\n",
    "            n=len(heights)\n",
    "\n",
    "            left_min=[0]*n\n",
    "            right_min=[0]*n\n",
    "            stack=[]\n",
    "            for i in range(n):\n",
    "                while stack and heights[stack[-1]]>=heights[i]:\n",
    "                    stack.pop()\n",
    "                left_min[i]=stack[-1] if stack else -1\n",
    "                stack.append(i)\n",
    "            stack=[]\n",
    "            for i in range(n-1,-1,-1):\n",
    "                while stack and heights[stack[-1]]>=heights[i]:\n",
    "                    stack.pop()\n",
    "                right_min[i]=stack[-1] if stack else n\n",
    "                stack.append(i)\n",
    "            ans=0\n",
    "            for i in range(n):\n",
    "                ans=max(ans,(right_min[i]-left_min[i]-1)*heights[i])\n",
    "            return ans  \n",
    "        \n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "\n",
    "        res=0\n",
    "        heights=[0]*n\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if matrix[i][j]=='1':\n",
    "                    heights[j]+=1\n",
    "                else:\n",
    "                    heights[j]=0\n",
    "            res=max(res,maxRectangle(heights))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        if not matrix:return 0\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        # 记录当前位置上方连续“1”的个数\n",
    "        pre=[0]*(n+1)\n",
    "        res=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 前缀和\n",
    "                pre[j]=pre[j]+1 if matrix[i][j]==\"1\" else 0\n",
    "\n",
    "            # 单调栈\n",
    "            stack=[-1]\n",
    "            for k,num in enumerate(pre):\n",
    "                while stack and pre[stack[-1]]>num:\n",
    "                    index=stack.pop()\n",
    "                    res=max(res,pre[index]*(k-stack[-1]-1))\n",
    "                stack.append(k)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximalRectangle(self, matrix: List[List[str]]) -> int:\n",
    "        heights = [0] * len(matrix[0])\n",
    "\n",
    "        maxArea = 0\n",
    "\n",
    "        for row in range(len(matrix)):\n",
    "\n",
    "            for col in range(len(matrix[row])):\n",
    "                \n",
    "                if  matrix[row][col] == \"1\":\n",
    "                    heights[col] += 1\n",
    "                else:\n",
    "                    heights[col] = 0\n",
    "            maxArea =  max(maxArea, self.largest(heights))\n",
    "        \n",
    "        return maxArea\n",
    "    \n",
    "    def largest(self,heights:List[int]) -> int:\n",
    "        res = 0\n",
    "        newHeights = [0]\n",
    "        newHeights.extend(heights)\n",
    "        newHeights.append(0)\n",
    "        print(newHeights)\n",
    "\n",
    "        stack = []\n",
    "        for i, v in enumerate(newHeights):\n",
    "            while stack and v < newHeights[stack[-1]]:\n",
    "                h = newHeights[stack[-1]]\n",
    "                stack.pop()\n",
    "                left = stack[-1]\n",
    "                right = i\n",
    "                w = right - left - 1\n",
    "                res = max(res, h * w)\n",
    "\n",
    "            stack.append(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
